package com.leetcode.www;

import java.util.ArrayList;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 就是9键输入
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-15
 * Time:20:05
 */
public class DFS17 {
    public static List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.length() == 0) {
            return list;
        }
        char[] ch = digits.toCharArray();
        int len = ch.length;
        boolean[] bool = new boolean[len];
        DFS(list,ch,len,0);
        return list;
    }
    public static StringBuilder sb = new StringBuilder();
    public static void DFS(List<String> list,char[] ch,int len,int begin){
        if(begin == len){
            list.add(new String(sb));
            return;
        }
        //当前应该干什么
        char c = ch[begin];
        if (c != '9' && c != '7' && c != '8') {//特殊情况写的有点麻烦了
            char[] ch2 = new char[3];
            int x = (Character.getNumericValue(c) - 2) * 3;
            for (int j = 0; j < 3; j++) {
                int w = x + j;
                ch2[j] = (char) ('a' + w);//开始的字符,可以用map代替 能简单点
                sb.append((char) ch2[j]);//加进每一个可以用的字符
                //下一步应该干什么   处理一个字符
                DFS(list, ch, len, begin + 1);
                sb.deleteCharAt(begin);//回溯 删除最后一个 此时的sb已经完成了一次的拼接需要回到上一步然后看其他可能
            }
        } else if( c == '9') {
            char[] ch2 = new char[4];
            for (int j = 0; j < 4; j++) {
                ch2[j] = (char) ('w' + j);
                sb.append((char) ch2[j]);
                DFS(list, ch, len, begin + 1);
                sb.deleteCharAt(begin);
            }
        }else if ( c == '7'){
            char[] ch2 = new char[4];
            for (int j = 0; j < 4; j++) {
                ch2[j] = (char) ('p' + j);
                sb.append((char) ch2[j]);
                DFS(list, ch, len, begin + 1);
                sb.deleteCharAt(begin);
            }
        }else{
            char[] ch2 = new char[3];
            for (int j = 0; j < 3; j++) {
                ch2[j] = (char) ('t' + j);
                sb.append((char) ch2[j]);
                DFS(list, ch, len, begin + 1);
                sb.deleteCharAt(begin);
            }
        }

    }
}
